package main

import (
	"fmt"
	"math"
)

// top 150 的集合

// 98. 验证二叉搜索树 https://leetcode.cn/problems/validate-binary-search-tree
func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isValidBSTSub(root, nil, nil)
}

// 一定要比 minVal 大 比 maxVal 小
func isValidBSTSub(root *TreeNode, minNode, maxNode *TreeNode) bool {
	if root == nil {
		return true
	}

	if minNode != nil && root.Val <= minNode.Val {
		return false
	}
	if maxNode != nil && root.Val >= maxNode.Val {
		return false
	}
	return isValidBSTSub(root.Left, minNode, root) && isValidBSTSub(root.Right, root, maxNode)
}

// 108. 将有序数组转换为二叉搜索树 https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
func sortedArrayToBST(nums []int) *TreeNode {
	return sortedArrayToBSTHelper(nums, 0, len(nums)-1)
}

func sortedArrayToBSTHelper(nums []int, start, end int) *TreeNode {
	if start > end {
		return nil
	}
	mid := (start + end) / 2
	root := &TreeNode{Val: nums[mid]}
	root.Left = sortedArrayToBSTHelper(nums, start, mid-1)
	root.Right = sortedArrayToBSTHelper(nums, mid+1, end)
	return root
}

// 230. 二叉搜索树中第K小的元素 https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description
func kthSmallest(root *TreeNode, k int) int {
	kthSmallVal = 0
	kthNum = 0
	traverse(root, k)
	return kthSmallVal
}

var kthSmallVal int
var kthNum int

func traverse(root *TreeNode, k int) {
	if root == nil {
		return
	}
	if kthNum >= k {
		return
	}

	traverse(root.Left, k)
	kthNum++
	if kthNum == k {
		kthSmallVal = root.Val
		return
	}
	traverse(root.Right, k)
}

// 222. 完全二叉树的节点个数 https://leetcode.cn/problems/count-complete-tree-nodes
func countNodes(root *TreeNode) int {
	if root == nil {
		return 0
	}
	p := root
	leftHeight := 0
	for p != nil {
		p = p.Left
		leftHeight++
	}
	p = root
	rightHeight := 0
	for p != nil {
		p = p.Right
		rightHeight++
	}
	if rightHeight == leftHeight {
		return int(math.Pow(2, float64(rightHeight)) - 1)
	}

	return 1 + countNodes(root.Left) + countNodes(root.Right)
}

// BSTIterator 173. 二叉搜索树迭代器 https://leetcode.cn/problems/binary-search-tree-iterator/
type BSTIterator struct {
	queue []int
}

func Constructor(root *TreeNode) BSTIterator {
	instance := BSTIterator{}
	instance.inorder(root)
	return instance
}

func (this *BSTIterator) inorder(root *TreeNode) {
	if root == nil {
		return
	}
	this.inorder(root.Left)
	this.queue = append(this.queue, root.Val)
	this.inorder(root.Right)
}

func (this *BSTIterator) Next() int {
	v := this.queue[0]
	this.queue = this.queue[1:]
	return v
}

func (this *BSTIterator) HasNext() bool {
	return len(this.queue) != 0
}

func main_106() {
	inorder := []int{2, 1}
	postorder := []int{2, 1}
	v := buildTree106(inorder, postorder)
	fmt.Println(v)
}

// 106. 从中序与后序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal
func buildTree106(inorder []int, postorder []int) *TreeNode {
	end := len(inorder) - 1
	return doBuildTree106(inorder, 0, end, postorder, 0, end)
}

func doBuildTree106(inorder []int, iStart, iEnd int, postorder []int, pStart, pEnd int) *TreeNode {
	if iStart > iEnd || pStart > pEnd {
		return nil
	}
	// postOrder 最后的元素是根节点
	rootVal := postorder[pEnd]
	rootPos := 0
	root := &TreeNode{Val: rootVal}
	leftNum := 0
	for i := iStart; i <= iEnd; i++ {
		if inorder[i] != rootVal {
			leftNum++
		} else {
			rootPos = i
			break
		}
	}
	root.Left = doBuildTree106(inorder, iStart, rootPos-1, postorder, pStart, pStart+leftNum-1)
	root.Right = doBuildTree106(inorder, rootPos+1, iEnd, postorder, pStart+leftNum, pEnd-1)
	return root
}

// 236. 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	// if root.left == p && root.right == q
	if root == p || root == q {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root
	}
	if left != nil {
		return left
	}
	return right
}

// 530. 二叉搜索树的最小绝对差 https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
var prev *TreeNode
var minVal int

// 这就是一个有序数组，中序遍历就是从头开始往后
func getMinimumDifference(root *TreeNode) int {
	minVal = math.MaxInt
	prev = nil
	dfs(root)
	return minVal
}

func dfs(node *TreeNode) {
	if node == nil {
		return
	}
	dfs(node.Left)
	if prev != nil {
		minVal = min(minVal, node.Val-prev.Val)
	}
	prev = node
	dfs(node.Right)
}

func min(v1, v2 int) int {
	if v1 > v2 {
		return v2
	}
	return v1
}

// 103. 二叉树的锯齿形层序遍历 https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
func zigzagLevelOrder(root *TreeNode) [][]int {
	queue := []*TreeNode{root}
	var res [][]int
	flag := false

	for len(queue) != 0 {
		size := len(queue)
		tmpRes := []int{}
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}

			if flag {
				tmpRes = append(tmpRes, node.Val)
			} else {
				tmpRes = append([]int{node.Val}, tmpRes...)
			}
		}
		res = append(res, tmpRes)
		flag = !flag
	}
	return res
}

func main_sumNumbers() {
	root := &TreeNode{Val: 4}
	root.Left = &TreeNode{Val: 9, Left: &TreeNode{Val: 5}, Right: &TreeNode{Val: 1}}
	root.Right = &TreeNode{Val: 0}

	root = &TreeNode{Val: 8}
	root.Left = &TreeNode{Val: 3, Left: nil, Right: &TreeNode{Val: 9, Left: &TreeNode{Val: 9}, Right: &TreeNode{Val: 5}}}
	root.Right = &TreeNode{Val: 5}

	v := sumNumbers(root)
	fmt.Println(v)
}

// 129求根节点到叶节点数字之和
func sumNumbers(root *TreeNode) int {
	sumNumbersRes = nil
	if root == nil {
		return 0
	}
	sumNumbersBacktrace(root, []int{})
	ans := 0
	for _, group := range sumNumbersRes {
		x := 0
		for _, v := range group {
			x = x*10 + v
		}
		ans += x
	}
	return ans
}

var sumNumbersRes [][]int

func sumNumbersBacktrace(root *TreeNode, num []int) {
	n := len(num)
	num = append(num, root.Val)
	if root.Left == nil && root.Right == nil {
		tmpData := make([]int, len(num))
		copy(tmpData, num)
		sumNumbersRes = append(sumNumbersRes, tmpData)
		num = num[:n:n]
		return
	}

	if root.Left != nil {
		sumNumbersBacktrace(root.Left, num)
	}
	if root.Right != nil {
		sumNumbersBacktrace(root.Right, num)
	}
	num = num[:n:n]
}

func levelOrderBottom(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	var res [][]int
	queue := []*TreeNode{root}
	for len(queue) != 0 {
		size := len(queue)
		tmpRes := []int{}
		for i := 0; i < size; i++ {
			node := queue[0]
			tmpRes = append(tmpRes, node.Val)
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		res = append(res, tmpRes)
	}
	size := len(res)
	for i := 0; i < size/2; i++ {
		res[i], res[size-i-1] = res[size-i-1], res[i]
	}
	return res
}

// 114. 二叉树展开为链表 https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	flatten(root.Right)
	flatten(root.Left)

	if root.Left == nil {
		return
	}

	// 左子树最后一个节点
	node := root.Left
	for node.Right != nil {
		node = node.Right
	}
	node.Right = root.Right
	root.Right = root.Left
	root.Left = nil
}

func averageOfLevels(root *TreeNode) []float64 {
	if root == nil {
		return []float64{0}
	}
	res := []float64{}
	queue := []*TreeNode{root}
	for len(queue) != 0 {
		size := len(queue)
		sum := 0
		for i := 0; i < size; i++ {
			// 出队列
			node := queue[0]
			queue = queue[1:]
			sum += node.Val
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		res = append(res, float64(sum)/float64(size))
	}
	return res
}

// 102. 二叉树的层序遍历
func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	var res [][]int
	queue := []*TreeNode{root}

	for len(queue) != 0 {
		size := len(queue)
		tmpRes := []int{}

		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			tmpRes = append(tmpRes, node.Val)

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		res = append(res, tmpRes)
	}
	return res
}

// 104. 二叉树的最大深度 https://leetcode.cn/problems/maximum-depth-of-binary-tree/
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max[int](maxDepth(root.Left), maxDepth(root.Right))
}

func max[T int | string](v1, v2 T) T {
	if v1 > v2 {
		return v1
	}
	return v2
}

// 105. 从前序与中序遍历序列构造二叉树
func buildTree(preorder []int, inorder []int) *TreeNode {
	n := len(preorder)
	return buildTreeSub(preorder, 0, n-1, inorder, 0, n-1)
}

func buildTreeSub(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int) *TreeNode {
	if preStart == preEnd {
		return &TreeNode{Val: preorder[preStart]}
	}
	if preStart > preEnd {
		return nil
	}
	// 根节点值
	rootVal := preorder[preStart]
	// 找到根节点下标
	rootIndex := inStart
	for inorder[rootIndex] != rootVal {
		rootIndex++
	}

	leftNum := rootIndex - inStart //左子树节点数量

	root := &TreeNode{Val: rootVal}
	root.Left = buildTreeSub(preorder, preStart+1, preStart+leftNum, inorder, inStart, rootIndex-1)
	root.Right = buildTreeSub(preorder, preStart+leftNum+1, preEnd, inorder, rootIndex+1, inEnd)
	return root
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
